/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

import java.util.*;

/**
 *
 * @author mac
 */
public class LC261 {

    static class Solution {

        /**
         * @param matrix: the matrix for calculation.
         * @return: return the max area after operation at most once.
         */
        public int maxArea(int[][] matrix) {
            // write your code here.
            int n = matrix.length;
            int m = matrix[0].length;
            UF uf = new UF();
            boolean[][] visited = new boolean[n][m];
            int ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (matrix[i][j] == 1) {
                        dfs(matrix, i, j, i * m + j, visited, uf);
                        if (uf.size.get(i * m + j) > ans) {
                            ans = uf.size.get(i * m + j);
                        }
                    }
                }
            }

            int[] dirx = {-1, 1, 0, 0};
            int[] diry = {0, 0, -1, 1};
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (matrix[i][j] == 0) {
                        //检查上下左右的并查集情况，每个方向如果有1合并进去
                        int curcnt = 1;
                        set.clear();
                        for (int k = 0; k < 4; k++) {
                            int x1 = i + dirx[k];
                            int y1 = j + diry[k];

                            int idx = x1 * m + y1;
                            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && matrix[x1][y1] == 1) {
                                int f1 = uf.parents.get(idx);
                                int cnt = uf.size.get(f1);
                                if (!set.contains(f1)) {
                                    curcnt += cnt;
                                }
                                set.add(f1);
                            }
                        }

                        if (ans < curcnt) {
                            ans = curcnt;
                        }
                    }
                }
            }

            return ans;
        }

        public void dfs(int[][] matrix, int i, int j, int pid, boolean[][] visited, UF uf) {
            int n = matrix.length;
            int m = matrix[0].length;
            if (i < 0 || j < 0 || i == n || j == m || visited[i][j] || matrix[i][j] == 0) {
                return;
            }
            int idx = i * m + j;
            uf.union(pid, idx);
            visited[i][j] = true;
            dfs(matrix, i - 1, j, pid, visited, uf);
            dfs(matrix, i + 1, j, pid, visited, uf);
            dfs(matrix, i, j - 1, pid, visited, uf);
            dfs(matrix, i, j + 1, pid, visited, uf);

        }

        static class UF {

            public Map<Integer, Integer> parents = new HashMap<>();
            public Map<Integer, Integer> size = new HashMap<>();
            public Map<Integer, Integer> help = new HashMap<>();
            public int sets = 0;

            public int find(int x) {
                if (!parents.containsKey(x)) {
                    parents.put(x, x);
                    size.put(x, 1);
                    sets++;
                }

                int hi = 0;
                while (x != parents.get(x)) {
                    help.put(hi++, x);
                    x = parents.get(x);
                }

                for (hi--; hi >= 0; hi--) {
                    parents.put(help.get(hi), x);
                }

                return x;
            }

            public void union(int a, int b) {
                int f1 = find(a);
                int f2 = find(b);
                if (f1 != f2) {
                    int s1 = size.get(f1);
                    int s2 = size.get(f2);
                    if (s1 >= s2) {
                        size.put(f1, s1 + s2);
                        parents.put(f2, f1);
                    } else {
                        size.put(f2, s1 + s2);
                        parents.put(f1, f2);
                    }
                    sets--;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[][] arr = {{0, 1}, {1, 0}};
        Solution obj = new Solution();
        System.out.println(obj.maxArea(arr));
        int[][] arr1 = {
            {0, 1},
            {1, 0},
            {1, 1}
        };
        System.out.println(obj.maxArea(arr1));
    }

}
